package 变长滑动窗口1

func lengthOfLongestSubstring(s string) (ans int) {
	charCount := map[byte]int{}
	n := len(s)
	left := 0
	right := -1
	for left < n {
		if left > 0 {
			delete(charCount, s[left-1])
		}
		for right+1 < n && charCount[s[right+1]] == 0 {
			charCount[s[right+1]]++
			right++
		}
		currentLen := right - left + 1
		ans = max(ans, currentLen)
		left++
	}
	return
}

//package main
//
//// lengthOfLongestSubstring 优化版：用数组记录字符最后出现位置，减少哈希操作
//func lengthOfLongestSubstring(s string) int {
//    // 用数组替代哈希表：假设字符为 ASCII 码（0-127），存储字符最后出现的索引
//    // 初始值为 -1，表示未出现过
//    lastOccurred := make([]int, 128)
//    for i := range lastOccurred {
//        lastOccurred[i] = -1
//    }
//
//    n := len(s)
//    maxLen := 0    // 最长无重复子串长度
//    left := 0      // 窗口左边界（当前窗口 [left, right]）
//
//    // 右指针遍历字符串，直接扩展窗口
//    for right := 0; right < n; right++ {
//        char := s[right]
//        // 当前字符最后出现的位置 >= left，说明在当前窗口内重复
//        // 左指针直接跳到 "最后出现位置 + 1"，确保窗口内无重复
//        if lastOccurred[char] >= left {
//            left = lastOccurred[char] + 1
//        }
//
//        // 更新当前字符的最后出现位置为 right
//        lastOccurred[char] = right
//
//        // 计算当前窗口长度，更新最大长度
//        currentLen := right - left + 1
//        if currentLen > maxLen {
//            maxLen = currentLen
//        }
//    }
//
//    return maxLen
//}

//// lengthOfLongestSubstring 用哈希表记录字符最后出现位置，寻找最长无重复子串
//func lengthOfLongestSubstring(s string) int {
//    // 哈希表：键为字符，值为该字符最后出现的索引（初始无记录，未出现的字符视为索引-1）
//    lastOccurred := make(map[rune]int)
//
//    n := len(s)
//    maxLen := 0    // 最长无重复子串长度
//    left := 0      // 窗口左边界（当前窗口 [left, right]）
//
//    // 右指针遍历字符串，扩展窗口
//    for right, char := range s {
//        // 若字符已出现过，且最后出现的位置在当前窗口内（>= left）
//        // 则将左指针移到“最后出现位置 + 1”，确保窗口内无重复
//        if lastIdx, exists := lastOccurred[char]; exists && lastIdx >= left {
//            left = lastIdx + 1
//        }
//
//        // 更新当前字符的最后出现位置为当前右指针索引
//        lastOccurred[char] = right
//
//        // 计算当前窗口长度，更新最大长度
//        currentLen := right - left + 1
//        if currentLen > maxLen {
//            maxLen = currentLen
//        }
//    }
//
//    return maxLen
//}
